package sort;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 各种排序方法(从小到大）
 * 1.冒泡排序
 * 2.选择排序
 * 3.插入排序
 * 4.希尔排序
 * 5.归并排序
 * 6.快速排序
 * 7.计数排序
 * 8.桶排序
 * 9.基数排序
 * 10.堆排序
 * 解释：
 *  稳定：排序前a=b并且a在b的前面，排序后a依然在b的前面
 *  不稳定：以上反之
 * @author HuWLin
 *
 * */
public class ArraySort {
    /*
    * 冒泡排序
    * 稳定
    * 时间复杂度为：
    *   最好情况为O(n)
    *   最坏情况为O(n ^ 2)
    *   平均O(n ^ 2)
    * 空间复杂度为O(1)
    * @param nums
    *       传入数组
    * */
    public void bubbleSort(int[] nums){
        int len = nums.length;
        for(int i = 0;i < len;i ++){
            //用来存放是否时排序好的，如果途中没有进行过交换直接结束，防止浪费时间
            boolean completed = true;
            for(int j = 1;j < len - i;j ++){
                if(nums[j - 1] > nums[j]){
                    int tmp = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = tmp;
                    completed = false;
                }
            }
            //全程没有经过换位置就说明是有顺序的直接结束
            if(completed){
                break;
            }
        }
    }

    /*
    * 选择排序
    * 不稳定
    * 时间复杂度为O(n ^ 2)
    * 空间复杂度为O(1)
    * @param nums
    *       传入数组
    * */
    public void selectSort(int[] nums){
        int len = nums.length;
        for(int i = 0;i < len;i ++){
            //用来存放最小的数的下标
            int min = i;
            //找到最小的数下表
            for(int j = i;j < len;j ++){
                if(nums[j] < nums[min]){
                    min = j;
                }
            }
            //把最小的数交换给第i个
            int tmp = nums[min];
            nums[min] = nums[i];
            nums[i] = tmp;
        }
    }

    /*
     * 插入排序
     * 稳定
     * 时间复杂度为：
     *   最好情况为O(n)
     *   最坏情况为O(n ^ 2)
     *   平均O(n ^ 2)
     * 空间复杂度为O(1)
     * @param nums
     *       传入数组
     * */
    public void insertSort(int[] nums){
        int len = nums.length;
        for(int i = 0;i < nums.length;i ++){
            int k = i;
            while(k > 0){
                //往前找，比自己大就交换
                if(nums[k] < nums[k - 1]){
                    int tmp = nums[k];
                    nums[k] = nums[k - 1];
                    nums[k - 1] = tmp;
                }else {
                    break;
                }
                k --;
            }
        }
    }

    /*
     * 希尔排序
     * 不稳定
     * 时间复杂度为：
     *   最好情况为O(n ^ 1.3)
     *   最坏情况为O(n ^ 2)
     *   平均O(n)
     * 空间复杂度为O(1)
     *
     * 具体解释放在md文件里
     * @param nums
     *       传入数组
     * */
    public void shellSort(int[] nums){
        int len = nums.length;
        //gap是一个增量
        for(int gap = len / 2;gap > 0;gap /= 2){
            //从最小增量开始遍历数组
            for(int i = gap;i < len;i ++){
                int j = i;
                //这里就是插入排序，只不过减一变成了减gap
                while(j - gap >= 0 && nums[j] < nums[j - gap]){
                    int tmp = nums[j];
                    nums[j] = nums[j - gap];
                    nums[j - gap] = tmp;
                    j -= gap;
                }
            }
        }
    }

    /*
     * 归并排序
     * 稳定
     * 时间复杂度为：O(n log2 n)
     * 空间复杂度为O(n)
     *
     * 具体解释放在md文件里
     * @param nums
     *       传入数组
     * @return
     *       返回排好序的数组
     * */
    public int[] mergeSort(int[] nums){
        int len = nums.length;
        //长度为1的时候直接返回本身
        if(len < 2){
            return nums;
        }
        //取中间分成两个数组
        int mid = len / 2;
        int[] left = Arrays.copyOfRange(nums,0,mid);
        int[] right = Arrays.copyOfRange(nums,mid,len);
        //这边进行了一个递归，一直找到长度为1的数组开始计算
        //先是拿出前两个比，再拿出前四个，再拿出前八个，以此类推，两部分进行分治
        return merge(mergeSort(left),mergeSort(right));
    }

    /*
    * 所需要用到的额外空间，将两个数组排好序的数组合成一个数组，递归会使最小长度为一，所以每一次用到的都是拍好的
    *
    * @param left
    *       数组前半部分
    * @param right
    *       数组后半部分
    *
    * @return
    *       返回两部分组合排序后的数组
    * */
    private int[] merge(int[] left,int[] right){
        int[] res = new int[left.length + right.length];
        //在此基础上两个数组都是排序好的，此处将两个数组组合成一个数组
        for(int l = 0,r = 0,i = 0;i < res.length;i ++){
            if(l >= left.length){
                res[i] = right[r ++];
            }else if(r >= right.length){
                res[i] = left[l ++];
            }else if(left[l] < right[r]){
                res[i] = left[l ++];
            }else {
                res[i] = right[r ++];
            }
        }
        return res;
    }

    /*
     * 快速排序
     * 不稳定
     * 时间复杂度为：
     *  最坏:O(n ^ 2)
     *  最好:O(n log2 n)
     *  平均:O(n log2 n)
     * 空间复杂度为O(n log2 n)
     *
     * 具体解释放在md文件中
     * @param nums
     *       传入数组
     * */
    public void quickSort(int[] nums){
        //进行递归
        quick(nums,0,nums.length - 1);
    }

    //这是挖坑法，和hoare基本没什么区别，个人感觉比较容易理解，因为挖坑
    private void quick(int[] nums,int left,int right){
        if(left < right){
            //每次开始把left位置的当作key，并且把这个位置挖坑
            int l = left,r = right,key = nums[left];
            while(l < r){
                //右边数字如果大于key那么向左移动，且要满足左边位置小于右边
                while(l < r && nums[r] >= key){
                    r --;
                }
                //在满足条件的情况下，把右边的数字填到之前留下的坑位，并且把这个位置当成新的坑位
                if(l < r){
                    nums[l ++] = nums[r];
                }
                //左边的数字如果小于key就向有移动，且要满足左边位置小于右边
                while(l < r && nums[l] < key){
                    l ++;
                }
                //满足条件的情况下，将左指针内容填到刚刚留下的坑位，并且把这个位置当场新的坑位
                if(l < r){
                    nums[r --] = nums[l];
                }
            }
            //在这个位置时l == r，所以此处下表为l或者r都可以
            nums[l] = key;
            //然后把左右两边进行分治，此时key数字下表左边的一定小于他，右边的大于等于他
            quick(nums,left,l - 1);
            quick(nums,r + 1,right);
        }
    }

    /*
     * 计数排序
     * 稳定
     * 时间复杂度为：O(n + k)
     * 空间复杂度为：O(n + k)
     * k为数组中最大数字减去最小数字加1
     * 排序速度受取值范围影响，只能是整数的数组。
     *
     * 具体解释放在md文件中
     * @param nums
     *       传入数组
     * */
    public void countSort(int[] nums){
        int min = nums[0],max = nums[0];
        //找出最大值和最小值
        for(int i : nums){
            if(i > max) {
                max = i;
            }
            if(i < min){
                min = i;
            }
        }
        //初始化一个数组，用来存放每个数值出现次数，为了节省空间和时间，这边用最大值减去最小值取长度
        int[] bucket = new int[max - min + 1];
        for(int i : nums){
            //进行统计，减去最小值后期可以加回来，用原数组值当成新数组的下标
            bucket[i - min] ++;
        }
        //numIndex用来记原数组的下表，bucketIndex用来及新数组下表
        for(int numIndex = 0,bucketIndex = 0;bucketIndex < bucket.length;){
            //如果等于0就说明原数组中没有这个数字，直接跳过
            if(bucket[bucketIndex] != 0){
                //bucketIndex + min是为了还原之前减掉的，
                nums[numIndex ++] = bucketIndex + min;
                bucket[bucketIndex] --;
            }else {
                bucketIndex ++;
            }
        }
    }

    /*
     * 桶排序
     * 不稳定
     * 时间复杂度为：
     *  最好：O(n)
     *  最差：O(n ^ 2)
     *  平均：O(n + k)
     * 空间复杂度为：O(n + k)
     *
     * 具体解释放在md文件中
     * @param nums
     *       传入列表
     * @return 返回排序后列表
     * */
    public ArrayList<Integer> bucketSort(ArrayList<Integer> nums){
        //这边的bucketBetween,100指的是每个桶所能容下的区间为100，比如第一个桶0-99，第二个桶100-199，可以重复
        return bucketSort(nums,100);
    }
    /*
    * 对于每一个桶进行排序，有些可能会使用其他排序，我这里尽量不使用其他排序，但会增加空间复杂度
    * 进行递归，一直到每一只桶里只存了1的范围
    * */
    private ArrayList<Integer> bucketSort(ArrayList<Integer> nums,int bucketBetween){
        if (nums == null || nums.size() < 2) {
            return nums;
        }
        //这边找出最大值和最小值，原理和计数排序类似
        int max = Integer.MIN_VALUE,min = Integer.MAX_VALUE;
        for(Integer i : nums){
            max = Math.max(i,max);
            min = Math.min(i,min);
        }
        //bucketSize是桶的数量
        int bucketSize = (max - min) / bucketBetween + 1;
        ArrayList<ArrayList<Integer>> bucket = new ArrayList<>(bucketSize);
        ArrayList<Integer> resArr = new ArrayList<>();
        //在每个桶中放列表
        for(int i = 0;i < bucketSize;i ++){
            bucket.add(new ArrayList<>());
        }
        //原理计数排序解释过，为什么要减min
        for (Integer num : nums) {
            bucket.get((num - min) / bucketBetween).add(num);
        }
        for(int i = 0;i < bucketSize;i ++){
            //这里就是上面提到的，当一个桶的区间为1的时候，进行结果统计，
            if(bucketBetween == 1){
                //处理重复数据
                if(bucket.get(i).size() > 0){
                    resArr.addAll(bucket.get(i));
                }
            }else {
                //若递归到只有一个桶时，每个桶取值区间减小
                if(bucketSize == 1){
                    bucketBetween --;
                }
                //这边实际上可以对当前桶进行排序，但我选择减少排序，使用递归，每一次递归的桶取值区间为当前除以2加1
                //加1是因为防止下一次桶的取值区间为0，0就没有意义了
                ArrayList<Integer> tmp = bucketSort(bucket.get(i),bucketBetween / 2 + 1);
                if(tmp.size() > 0){
                    //把数据放到需要返回的列表中
                    resArr.addAll(tmp);
                }
            }
        }
        return resArr;
    }


    /*
     * 基数排序
     * 稳定
     * 时间复杂度为：O(n * k)
     * 空间复杂度为：O(n + k)
     *
     * 具体解释放在md文件中
     * @param nums
     *       传入数组
     * */
    public void radixSort(int[] nums){
        int max = Integer.MIN_VALUE;
        for(Integer i : nums){
            max = Math.max(i,max);
        }
        int maxTen = 0;
        //这里是找到最大值的max，计算极大值有几位
        while(max > 0){
            maxTen ++;
            max /= 10;
        }
        //这边桶默认只给10的长度
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(10);
        for(int i = 0;i < 10;i ++){
            buckets.add(new ArrayList<>());
        }
        //mod指的是取余，div是除数，简单的理解就是从个位数排序，一直到最大为
        //初始化10和1，取个位数，100和10取十位数，例如123 % 10 / 1 = 3,123 % 100 / 10 = 2
        for(int i = 0,mod = 10,div = 1;i < maxTen;i ++,mod *= 10,div *= 10){
            //把每个数对应位放进对应桶里
            for (int value : nums) {
                int num = value % mod / div;
                buckets.get(num).add(value);
            }
            int index = 0;
            //把当前排好的数据放回数组
            for(ArrayList<Integer> bucket : buckets){
                for(Integer value : bucket){
                    nums[index ++] = value;
                }
                //当前桶里数组放回数组后，清空
                bucket.clear();
            }
        }
    }

    /*
     * 堆排序
     * 不稳定
     * 时间复杂度为：O(n log2 n)
     * 空间复杂度为：O(1)
     *
     * 具体解释放在md文件中
     * @param nums
     *       传入数组
     * */
    public void heapSort(int[] nums){
        int len = nums.length;
        //初始化一个大顶堆
        buildMaxHeap(nums,len);
        //初始化完成后，最上面的肯定是最大的，然后于最后一个进行交换，并且长度要进行减1
        for(int i = len - 1;i > 0;i --){
            swap(nums,i,0);
            len --;
            //交换完成之后要重新调整大顶堆，因为交换后最大的就不在最上面了，因为len--所以不会影响到最后一个最大的
            heap(nums,0,len);
        }
    }

    //初始化一个大顶堆，就是每一个非叶子结点都要大于他的子节点
    private void buildMaxHeap(int[] nums,int len){
        //从最后一个非叶子结点开始进行初始化
        for(int i = (int) (Math.floor((double) len / 2) - 1); i >= 0; i --){
            heap(nums,i,len);
        }
    }

    //初始化大顶堆主要内容
    private void heap(int[] nums,int i,int len){
        //左子节点
        int left = i * 2 + 1;
        //右子节点
        int right = i * 2 + 2;
        int max = i;
        //找出最大值
        if(left < len && nums[left] > nums[max]){
            max = left;
        }
        if(right < len && nums[right] > nums[max]){
            max = right;
        }
        //若最大值不是i则进行交换
        if(max != i){
            swap(nums,i,max);
            //若子节点也是非叶子结点，也需要进行调整
            heap(nums,max,len);
        }
    }
    //交换方法
    private void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
